/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

#include "precomp.hpp"

CV_IMPL void cvCanny(const void* srcarr, void* dstarr,
                     double low_thresh, double high_thresh,
                     int aperture_size) {
    cv::Ptr<CvMat> dx, dy;
    cv::AutoBuffer<char> buffer;
    std::vector<uchar*> stack;
    uchar** stack_top = 0, **stack_bottom = 0;

    CvMat srcstub, *src = cvGetMat(srcarr, &srcstub);
    CvMat dststub, *dst = cvGetMat(dstarr, &dststub);
    CvSize size;
    int flags = aperture_size;
    int low, high;
    int* mag_buf[3];
    uchar* map;
    int mapstep, maxsize;
    int i, j;
    CvMat mag_row;

    if (CV_MAT_TYPE(src->type) != CV_8UC1 ||
            CV_MAT_TYPE(dst->type) != CV_8UC1) {
        CV_Error(CV_StsUnsupportedFormat, "");
    }

    if (!CV_ARE_SIZES_EQ(src, dst)) {
        CV_Error(CV_StsUnmatchedSizes, "");
    }

    if (low_thresh > high_thresh) {
        double t;
        CV_SWAP(low_thresh, high_thresh, t);
    }

    aperture_size &= INT_MAX;
    if ((aperture_size & 1) == 0 || aperture_size < 3 || aperture_size > 7) {
        CV_Error(CV_StsBadFlag, "");
    }

    size = cvGetMatSize(src);

    dx = cvCreateMat(size.height, size.width, CV_16SC1);
    dy = cvCreateMat(size.height, size.width, CV_16SC1);
    cvSobel(src, dx, 1, 0, aperture_size);
    cvSobel(src, dy, 0, 1, aperture_size);

    /*if( icvCannyGetSize_p && icvCanny_16s8u_C1R_p && !(flags & CV_CANNY_L2_GRADIENT) )
    {
        int buf_size=  0;
        IPPI_CALL( icvCannyGetSize_p( size, &buf_size ));
        CV_CALL( buffer = cvAlloc( buf_size ));
        IPPI_CALL( icvCanny_16s8u_C1R_p( (short*)dx->data.ptr, dx->step,
                                     (short*)dy->data.ptr, dy->step,
                                     dst->data.ptr, dst->step,
                                     size, (float)low_thresh,
                                     (float)high_thresh, buffer ));
        EXIT;
    }*/

    if (flags & CV_CANNY_L2_GRADIENT) {
        Cv32suf ul, uh;
        ul.f = (float)low_thresh;
        uh.f = (float)high_thresh;

        low = ul.i;
        high = uh.i;
    } else {
        low = cvFloor(low_thresh);
        high = cvFloor(high_thresh);
    }

    buffer.allocate((size.width + 2) * (size.height + 2) + (size.width + 2) * 3 * sizeof(int));

    mag_buf[0] = (int*)(char*)buffer;
    mag_buf[1] = mag_buf[0] + size.width + 2;
    mag_buf[2] = mag_buf[1] + size.width + 2;
    map = (uchar*)(mag_buf[2] + size.width + 2);
    mapstep = size.width + 2;

    maxsize = MAX(1 << 10, size.width * size.height / 10);
    stack.resize(maxsize);
    stack_top = stack_bottom = &stack[0];

    memset(mag_buf[0], 0, (size.width + 2)*sizeof(int));
    memset(map, 1, mapstep);
    memset(map + mapstep * (size.height + 1), 1, mapstep);

    /* sector numbers
       (Top-Left Origin)

        1   2   3
         *  *  *
          * * *
        0*******0
          * * *
         *  *  *
        3   2   1
    */

#define CANNY_PUSH(d)    *(d) = (uchar)2, *stack_top++ = (d)
#define CANNY_POP(d)     (d) = *--stack_top

    mag_row = cvMat(1, size.width, CV_32F);

    // calculate magnitude and angle of gradient, perform non-maxima supression.
    // fill the map with one of the following values:
    //   0 - the pixel might belong to an edge
    //   1 - the pixel can not belong to an edge
    //   2 - the pixel does belong to an edge
    for (i = 0; i <= size.height; i++) {
        int* _mag = mag_buf[(i > 0) + 1] + 1;
        float* _magf = (float*)_mag;
        const short* _dx = (short*)(dx->data.ptr + dx->step * i);
        const short* _dy = (short*)(dy->data.ptr + dy->step * i);
        uchar* _map;
        int x, y;
        int magstep1, magstep2;
        int prev_flag = 0;

        if (i < size.height) {
            _mag[-1] = _mag[size.width] = 0;

            if (!(flags & CV_CANNY_L2_GRADIENT))
                for (j = 0; j < size.width; j++) {
                    _mag[j] = abs(_dx[j]) + abs(_dy[j]);
                }
            /*else if( icvFilterSobelVert_8u16s_C1R_p != 0 ) // check for IPP
            {
                // use vectorized sqrt
                mag_row.data.fl = _magf;
                for( j = 0; j < size.width; j++ )
                {
                    x = _dx[j]; y = _dy[j];
                    _magf[j] = (float)((double)x*x + (double)y*y);
                }
                cvPow( &mag_row, &mag_row, 0.5 );
            }*/
            else {
                for (j = 0; j < size.width; j++) {
                    x = _dx[j]; y = _dy[j];
                    _magf[j] = (float)std::sqrt((double)x * x + (double)y * y);
                }
            }
        } else {
            memset(_mag - 1, 0, (size.width + 2)*sizeof(int));
        }

        // at the very beginning we do not have a complete ring
        // buffer of 3 magnitude rows for non-maxima suppression
        if (i == 0) {
            continue;
        }

        _map = map + mapstep * i + 1;
        _map[-1] = _map[size.width] = 1;

        _mag = mag_buf[1] + 1; // take the central row
        _dx = (short*)(dx->data.ptr + dx->step * (i - 1));
        _dy = (short*)(dy->data.ptr + dy->step * (i - 1));

        magstep1 = (int)(mag_buf[2] - mag_buf[1]);
        magstep2 = (int)(mag_buf[0] - mag_buf[1]);

        if ((stack_top - stack_bottom) + size.width > maxsize) {
            int sz = (int)(stack_top - stack_bottom);
            maxsize = MAX(maxsize * 3 / 2, maxsize + 8);
            stack.resize(maxsize);
            stack_bottom = &stack[0];
            stack_top = stack_bottom + sz;
        }

        for (j = 0; j < size.width; j++) {
#define CANNY_SHIFT 15
#define TG22  (int)(0.4142135623730950488016887242097*(1<<CANNY_SHIFT) + 0.5)

            x = _dx[j];
            y = _dy[j];
            int s = x ^ y;
            int m = _mag[j];

            x = abs(x);
            y = abs(y);
            if (m > low) {
                int tg22x = x * TG22;
                int tg67x = tg22x + ((x + x) << CANNY_SHIFT);

                y <<= CANNY_SHIFT;

                if (y < tg22x) {
                    if (m > _mag[j - 1] && m >= _mag[j + 1]) {
                        if (m > high && !prev_flag && _map[j - mapstep] != 2) {
                            CANNY_PUSH(_map + j);
                            prev_flag = 1;
                        } else {
                            _map[j] = (uchar)0;
                        }
                        continue;
                    }
                } else if (y > tg67x) {
                    if (m > _mag[j + magstep2] && m >= _mag[j + magstep1]) {
                        if (m > high && !prev_flag && _map[j - mapstep] != 2) {
                            CANNY_PUSH(_map + j);
                            prev_flag = 1;
                        } else {
                            _map[j] = (uchar)0;
                        }
                        continue;
                    }
                } else {
                    s = s < 0 ? -1 : 1;
                    if (m > _mag[j + magstep2 - s] && m > _mag[j + magstep1 + s]) {
                        if (m > high && !prev_flag && _map[j - mapstep] != 2) {
                            CANNY_PUSH(_map + j);
                            prev_flag = 1;
                        } else {
                            _map[j] = (uchar)0;
                        }
                        continue;
                    }
                }
            }
            prev_flag = 0;
            _map[j] = (uchar)1;
        }

        // scroll the ring buffer
        _mag = mag_buf[0];
        mag_buf[0] = mag_buf[1];
        mag_buf[1] = mag_buf[2];
        mag_buf[2] = _mag;
    }

    // now track the edges (hysteresis thresholding)
    while (stack_top > stack_bottom) {
        uchar* m;
        if ((stack_top - stack_bottom) + 8 > maxsize) {
            int sz = (int)(stack_top - stack_bottom);
            maxsize = MAX(maxsize * 3 / 2, maxsize + 8);
            stack.resize(maxsize);
            stack_bottom = &stack[0];
            stack_top = stack_bottom + sz;
        }

        CANNY_POP(m);

        if (!m[-1]) {
            CANNY_PUSH(m - 1);
        }
        if (!m[1]) {
            CANNY_PUSH(m + 1);
        }
        if (!m[-mapstep - 1]) {
            CANNY_PUSH(m - mapstep - 1);
        }
        if (!m[-mapstep]) {
            CANNY_PUSH(m - mapstep);
        }
        if (!m[-mapstep + 1]) {
            CANNY_PUSH(m - mapstep + 1);
        }
        if (!m[mapstep - 1]) {
            CANNY_PUSH(m + mapstep - 1);
        }
        if (!m[mapstep]) {
            CANNY_PUSH(m + mapstep);
        }
        if (!m[mapstep + 1]) {
            CANNY_PUSH(m + mapstep + 1);
        }
    }

    // the final pass, form the final image
    for (i = 0; i < size.height; i++) {
        const uchar* _map = map + mapstep * (i + 1) + 1;
        uchar* _dst = dst->data.ptr + dst->step * i;

        for (j = 0; j < size.width; j++) {
            _dst[j] = (uchar) - (_map[j] >> 1);
        }
    }
}

void cv::Canny(const Mat& image, Mat& edges,
               double threshold1, double threshold2,
               int apertureSize, bool L2gradient) {
    Mat src = image;
    edges.create(src.size(), CV_8U);
    CvMat _src = src, _dst = edges;
    cvCanny(&_src, &_dst, threshold1, threshold2,
            apertureSize + (L2gradient ? CV_CANNY_L2_GRADIENT : 0));
}

/* End of file. */
